// 101. 对称二叉树

// 给定一个二叉树，检查它是否是镜像对称的。

// 例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
//     1
//    / \
//   2   2
//  / \ / \
// 3  4 4  3

// 但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
//     1
//    / \
//   2   2
//    \   \
//    3    3

const { TreeNode } = require("./common.js");

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isSymmetric = function (root) {
  // return check1(root, root);
  return check2(root, root);
};

/**
 * 递归
 * 
 * @param {TreeNode} a 二叉树
 * @param {TreeNode} b 二叉树
 * @returns 是否对称
 */
var check1 = function (a, b) {
  if (!a && !b) {
    return true;
  }
  if (!a || !b) {
    return false;
  }
  return a.val === b.val && check1(a.left, b.right) && check1(a.right, b.left);
};

/**
 * 迭代
 * 
 * @param {TreeNode} a 二叉树
 * @param {TreeNode} b 二叉树
 * @returns 是否对称
 */
var check2 = function(a, b) {
  const l = [];
  l.push(a);
  l.push(b);
  while(l.length) {
    a = l.shift();
    b = l.shift();
    if (!a && !b) {
      continue;
    }
    if ((!a || !b) || a.val != b.val) {
      return false;
    }
    l.push(a.left);
    l.push(b.right);
    l.push(a.right);
    l.push(b.left);
  }
  return true;
}

console.log(
  isSymmetric(
    new TreeNode(
      1,
      new TreeNode(2, new TreeNode(3, null, null), new TreeNode(4, null, null)),
      new TreeNode(2, new TreeNode(4, null, null), new TreeNode(3, null, null))
    )
  )
);
console.log(
  isSymmetric(
    new TreeNode(
      1,
      new TreeNode(2, null, new TreeNode(3, null, null)),
      new TreeNode(2, null, new TreeNode(3, null, null))
    )
  )
);
